<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/12/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/12/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/14/156/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/14/156/" itemprop="url">大整数四则运算</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-14T23:29:00+00:00">
                2017-02-14
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">//#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">struct bign&#123;</span><br><span class="line">    int d[1000];</span><br><span class="line">    int len;</span><br><span class="line">    bign()&#123;</span><br><span class="line">        memset(d,0,sizeof(d));</span><br><span class="line">        len = 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line">bign change(char str[])&#123;</span><br><span class="line">    bign a;</span><br><span class="line">    a.len = strlen(str);</span><br><span class="line">    for(int i = 0; i &lt; a.len ; i++)&#123;</span><br><span class="line">        a.d[i] = str[a.len - i - 1] - &apos;0&apos;;</span><br><span class="line">    &#125;</span><br><span class="line">    return a;</span><br><span class="line">&#125;</span><br><span class="line">bign add(bign a,bign b)&#123;</span><br><span class="line">    bign c;</span><br><span class="line">    int carry = 0;//进位</span><br><span class="line">    for(int i = 0; i &lt; a.len || i &lt; b.len; i++)&#123;</span><br><span class="line">        int temp = a.d[i] + b.d[i] + carry;</span><br><span class="line">        c.d[c.len++] = temp % 10;</span><br><span class="line">        carry = temp / 10;</span><br><span class="line">    &#125;</span><br><span class="line">    if (carry != 0 ) &#123;</span><br><span class="line">        c.d[c.len++] = carry;</span><br><span class="line">    &#125;</span><br><span class="line">    return c;</span><br><span class="line">&#125;</span><br><span class="line">bign sub(bign a,bign b)&#123;</span><br><span class="line">    bign c;</span><br><span class="line">    for (int i = 0; i &lt; a.len || i &lt; b .len; i++) &#123;</span><br><span class="line">        //以较长的为界限</span><br><span class="line">        if (a.d[i] &lt; b.d[i]) &#123;</span><br><span class="line">            a.d[i + 1]--;//借位</span><br><span class="line">            a.d[i]+=10;</span><br><span class="line">        &#125;</span><br><span class="line">        c.d[c.len++] = a.d[i] - b.d[i];//减法的结果为当前位结果</span><br><span class="line">    &#125;</span><br><span class="line">    while (c.len - 1 &gt;= 1 &amp;&amp; c.d[c.len - 1] == 0) &#123;</span><br><span class="line">        c.len--;//去除最高位的0</span><br><span class="line">    &#125;</span><br><span class="line">    return c;</span><br><span class="line">&#125;</span><br><span class="line">bign multi(bign a, int b)&#123;</span><br><span class="line">    bign c;</span><br><span class="line">    int carry = 0;//进位</span><br><span class="line">    for (int i = 0; i &lt; a.len; i++) &#123;</span><br><span class="line">        int temp = a.d[i] * b + carry;</span><br><span class="line">        c.d[c.len++] = temp % 10;//个位作为该位结果</span><br><span class="line">        carry = temp / 10;//高位部分作为新的进位</span><br><span class="line">    &#125;</span><br><span class="line">    while (carry != 0) &#123;</span><br><span class="line">        //和加法不一样，乘法的进位可能不止一位，因此用while</span><br><span class="line">        c.d[c.len++] = carry % 10;</span><br><span class="line">        carry /= 10;</span><br><span class="line">    &#125;</span><br><span class="line">    return c;</span><br><span class="line">&#125;</span><br><span class="line">bign divide (bign a,int b, int &amp;r)&#123;//高精度除法，r为余数</span><br><span class="line">    bign c;</span><br><span class="line">    c.len = a.len;//被除数的每一位和商的每一位是一一对应的，因此先令长度相等</span><br><span class="line">    for (int i = a.len - 1; i &gt;= 0; i--) &#123;</span><br><span class="line">        r = r * 10 + a.d[i];//和上一位遗留的余数组合</span><br><span class="line">        if (r &lt; b) c.d[i] = 0; //不够除，该位为0</span><br><span class="line">        else &#123;</span><br><span class="line">            //够除</span><br><span class="line">            c.d[i] = r / b;//商</span><br><span class="line">            r = r % b;//获得新的余数</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while (c.len - 1 &gt;= 1 &amp;&amp; c.d[c.len - 1] == 0) &#123;</span><br><span class="line">        c.len--;//去除高位的0，同时至少保留一位的最低位</span><br><span class="line">    &#125;</span><br><span class="line">    return c;</span><br><span class="line">&#125;</span><br><span class="line">void print(bign a)&#123;</span><br><span class="line">    for (int i = a.len - 1; i &gt;= 0; i--) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, a.d[i]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    char str1[1000], str2[1000];</span><br><span class="line">    int b;</span><br><span class="line">    scanf(&quot;%s%d&quot;, str1, &amp;b);</span><br><span class="line">    bign a = change(str1);</span><br><span class="line">//    bign b = change(str2);</span><br><span class="line">    int r;</span><br><span class="line">    print(divide(a, b, r));</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/13/155/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/13/155/" itemprop="url">PAT A1059</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-13T23:11:27+00:00">
                2017-02-13
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 <em> p2^k2 </em>…*pm^km.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case which gives a positive integer N in the range of long int.</p>
<p>Output Specification:</p>
<p>Factor N in the format N = p1^k1 <em> p2^k2 </em>…*pm^km, where pi’s are prime factors of N in increasing order, and the exponent ki is the number of pi – hence when there is only one pi, ki is 1 and must NOT be printed out.</p>
<p>Sample Input:<br>97532468<br>Sample Output:<br>97532468=2^2<em>11</em>17<em>101</em>1291</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 1000001;</span><br><span class="line">int prime[maxn], pnum = 0;</span><br><span class="line">bool p[maxn] = &#123;0&#125;;</span><br><span class="line">void Find_Prime(int n) &#123;//筛法出素数表</span><br><span class="line">	for (int i = 2; i &lt; maxn; i++) &#123;</span><br><span class="line">		if(p[i] == false)&#123;</span><br><span class="line">			prime[pnum++] = i;</span><br><span class="line">			if(pnum &gt;= n)break;//只要n个素数</span><br><span class="line">			for(int j = i + i ; j &lt; maxn; j += i)&#123;</span><br><span class="line">				p[j] = true;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">struct factor&#123;</span><br><span class="line">	int x,cnt;</span><br><span class="line">&#125;fac[10];</span><br><span class="line">int main()&#123;</span><br><span class="line">	Find_Prime(100010);</span><br><span class="line">	int n, num = 0;//num 为n的不同质因子的个数</span><br><span class="line">	scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">	if(n == 1) printf(&quot;1=1&quot;);</span><br><span class="line">	else &#123;</span><br><span class="line">		printf(&quot;%d=&quot;, n);</span><br><span class="line">		int sqr = (int)sqrt(1.0 * n);//n的根号</span><br><span class="line">		for (int i = 0;i &lt; pnum &amp;&amp; prime[i] &lt;= sqr;i++)&#123;//枚举sqr以内的质数</span><br><span class="line">			if(n % prime[i] == 0)&#123;</span><br><span class="line">				fac[num].x = prime[i];//记录该因子</span><br><span class="line">				fac[num].cnt = 0;</span><br><span class="line">				while(n % prime[i] == 0)&#123;</span><br><span class="line">					fac[num].cnt++;</span><br><span class="line">					n /= prime[i];</span><br><span class="line">				&#125;</span><br><span class="line">				num++;</span><br><span class="line">			&#125;</span><br><span class="line">			if(n == 1) break;</span><br><span class="line">		&#125;</span><br><span class="line">		if(n != 1)&#123;//如果无法被根号n以内的质因子除尽</span><br><span class="line">			fac[num].x = n;//那么一定有一个大于根号n的质因子</span><br><span class="line">			fac[num++].cnt = 1;</span><br><span class="line">		&#125;</span><br><span class="line">		//按格式输出结果</span><br><span class="line">		for (int i = 0; i &lt; num; i++)&#123;</span><br><span class="line">			if(i &gt; 0) printf(&quot;*&quot;);</span><br><span class="line">			printf(&quot;%d&quot;, fac[i].x);</span><br><span class="line">			if(fac[i].cnt &gt;1)&#123;</span><br><span class="line">				printf(&quot;^%d&quot;,fac[i].cnt);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>感想：筛法出素数表真的吊……没数学头脑的我只能看看了……<br>再弄记录一个常规的出素数表的方法<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">const int maxn = 1000001;</span><br><span class="line">int prime[maxn], pnum = 0;</span><br><span class="line"></span><br><span class="line">bool is_prime(int n)&#123;//判断n是否为素数</span><br><span class="line">	if(n == 1) return false;</span><br><span class="line">	int sqr = (int)sqrt(1.0 * n);</span><br><span class="line">	for (int i = 2; i &lt;= sqr ; i++)&#123;</span><br><span class="line">		if(n % i == 0) return false;</span><br><span class="line">	&#125;</span><br><span class="line">	return true;</span><br><span class="line">&#125;</span><br><span class="line">int p[maxn], pnum = 0;</span><br><span class="line">void Find_Prime()&#123;//打印素数表</span><br><span class="line">	for(int i = 1; i &lt; maxn; i++)&#123;</span><br><span class="line">		if(is_prime(i) == true)</span><br><span class="line">			prime[pnum++] = i;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/13/154/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/13/154/" itemprop="url">PAT B1013</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-13T22:40:00+00:00">
                2017-02-13
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>令Pi表示第i个素数。现任给两个正整数M &lt;= N &lt;= 104，请输出PM到PN的所有素数。</p>
<p>输入格式：</p>
<p>输入在一行中给出M和N，其间以空格分隔。</p>
<p>输出格式：</p>
<p>输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。</p>
<p>输入样例：<br>5 27<br>输出样例：<br>11 13 17 19 23 29 31 37 41 43<br>47 53 59 61 67 71 73 79 83 89<br>97 101 103<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 1000001;</span><br><span class="line">int prime[maxn], num = 0;</span><br><span class="line">bool p[maxn] = &#123;0&#125;;//如果i为素数，则p[i]为false；</span><br><span class="line">void Find_Prime(int n)&#123;</span><br><span class="line">    for (int i = 2; i &lt; maxn; i++) &#123;//从2开始</span><br><span class="line">        if (p[i] == false) &#123;//如果i是素数</span><br><span class="line">            prime[num++] = i;//计入</span><br><span class="line">            if (num &gt;= n) &#123;</span><br><span class="line">                break;</span><br><span class="line">            &#125;</span><br><span class="line">            for (int j = i + i; j &lt; maxn; j += i) &#123;</span><br><span class="line">                //筛去所有的i的倍数，循环条件不能写成j&lt;= maxn</span><br><span class="line">                p[j] = true;</span><br><span class="line">            &#125;</span><br><span class="line">            </span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">	int m, n, count = 0;</span><br><span class="line">	scanf(&quot;%d%d&quot;, &amp;m, &amp;n);</span><br><span class="line">	Find_Prime(n);</span><br><span class="line">	for (int i = m ; i &lt;= n ; i++) &#123;</span><br><span class="line">		printf(&quot;%d&quot;, prime[i - 1]);</span><br><span class="line">		count++;</span><br><span class="line">		if(count % 10 != 0 &amp;&amp; i &lt; n) printf(&quot; &quot;);</span><br><span class="line">		else printf(&quot;\n&quot;);</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/13/153/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/13/153/" itemprop="url">PAT B1019/A1069</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-13T21:59:40+00:00">
                2017-02-13
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>给定任一个各位数字不完全相同的4位正整数，如果我们先把4个数字按非递增排序，再按非递减排序，然后用第1个数字减第2个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的6174，这个神奇的数字也叫Kaprekar常数。</p>
<p>例如，我们从6767开始，将得到</p>
<p>7766 - 6677 = 1089<br>9810 - 0189 = 9621<br>9621 - 1269 = 8352<br>8532 - 2358 = 6174<br>7641 - 1467 = 6174<br>… …</p>
<p>现给定任意4位正整数，请编写程序演示到达黑洞的过程。</p>
<p>输入格式：</p>
<p>输入给出一个(0, 10000)区间内的正整数N。</p>
<p>输出格式：</p>
<p>如果N的4位数字全相等，则在一行内输出“N - N = 0000”；否则将计算的每一步在一行内输出，直到6174作为差出现，输出格式见样例。注意每个数字按4位数格式输出。</p>
<p>输入样例1：<br>6767<br>输出样例1：<br>7766 - 6677 = 1089<br>9810 - 0189 = 9621<br>9621 - 1269 = 8352<br>8532 - 2358 = 6174<br>输入样例2：<br>2222<br>输出样例2：<br>2222 - 2222 = 0000</p>
<p>For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end up at the number 6174 – the “black hole” of 4-digit numbers. This number is named Kaprekar Constant.</p>
<p>For example, start from 6767, we’ll get:</p>
<p>7766 - 6677 = 1089<br>9810 - 0189 = 9621<br>9621 - 1269 = 8352<br>8532 - 2358 = 6174<br>7641 - 1467 = 6174<br>… …</p>
<p>Given any 4-digit number, you are supposed to illustrate the way it gets into the black hole.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case which gives a positive integer N in the range (0, 10000).</p>
<p>Output Specification:</p>
<p>If all the 4 digits of N are the same, print in one line the equation “N - N = 0000”. Else print each step of calculation in a line until 6174 comes out as the difference. All the numbers must be printed as 4-digit numbers.</p>
<p>Sample Input 1:<br>6767<br>Sample Output 1:<br>7766 - 6677 = 1089<br>9810 - 0189 = 9621<br>9621 - 1269 = 8352<br>8532 - 2358 = 6174<br>Sample Input 2:<br>2222<br>Sample Output 2:<br>2222 - 2222 = 0000<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">bool cmp (int a, int b)&#123;</span><br><span class="line">	return a &gt; b;</span><br><span class="line">&#125;</span><br><span class="line">void to_array (int n, int num[])&#123;</span><br><span class="line">	for (int i = 0; i &lt; 4; i++) &#123;</span><br><span class="line">		num[i] = n % 10;</span><br><span class="line">		n /= 10;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">int to_number (int num[]) &#123;</span><br><span class="line">	int sum = 0;</span><br><span class="line">	for (int i = 0; i &lt; 4; i++) &#123;</span><br><span class="line">		sum = sum * 10 + num[i];</span><br><span class="line">	&#125;</span><br><span class="line">	return sum;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">	int n, Min, Max;</span><br><span class="line">	scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">	int num[5];</span><br><span class="line">	while(1)&#123;</span><br><span class="line">		to_array(n, num);</span><br><span class="line">		sort(num , num + 4);//从小到大</span><br><span class="line">		Min = to_number(num);</span><br><span class="line">		sort(num , num + 4 ,cmp);//从大到小</span><br><span class="line">		Max = to_number(num);</span><br><span class="line">		n = Max - Min;</span><br><span class="line">		printf(&quot;%04d - %04d = %04d\n&quot;, Max, Min, n);</span><br><span class="line">		if( n == 0 || n == 6174) break;</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/13/152/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/13/152/" itemprop="url">浙大提前查分</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-13T17:25:00+00:00">
                2017-02-13
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/默认/" itemprop="url" rel="index">
                    <span itemprop="name">默认</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>[paste.ubuntu.com/23987628][1] [1]: <a href="http://paste.ubuntu.com/23987628" target="_blank" rel="noopener">http://paste.ubuntu.com/23987628</a></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/13/151/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/13/151/" itemprop="url">PAT B1045/A1101</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-13T00:32:55+00:00">
                2017-02-13
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?</p>
<p>For example, given N = 5 and the numbers 1, 3, 2, 4, and 5. We have:</p>
<p>1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;<br>3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;<br>2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;<br>and for the similar reason, 4 and 5 could also be the pivot.<br>Hence in total there are 3 pivot candidates.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line gives a positive integer N (&lt;= 105). Then the next line contains N distinct positive integers no larger than 109. The numbers in a line are separated by spaces.</p>
<p>Output Specification:</p>
<p>For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.</p>
<p>Sample Input:<br>5<br>1 3 2 4 5<br>Sample Output:<br>3<br>1 4 5</p>
<p>著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？</p>
<p>例如给定N = 5, 排列是1、3、2、4、5。则：</p>
<p>1的左边没有元素，右边的元素都比它大，所以它可能是主元；<br>尽管3的左边元素都比它小，但是它右边的2它小，所以它不能是主元；<br>尽管2的右边元素都比它大，但其左边的3比它大，所以它不能是主元；<br>类似原因，4和5都可能是主元。<br>因此，有3个元素可能是主元。</p>
<p>输入格式：</p>
<p>输入在第1行中给出一个正整数N（&lt;= 105）； 第2行是空格分隔的N个不同的正整数，每个数不超过109。</p>
<p>输出格式：</p>
<p>在第1行中输出有可能是主元的元素个数；在第2行中按递增顺序输出这些元素，其间以1个空格分隔，行末不得有多余空格。</p>
<p>输入样例：<br>5<br>1 3 2 4 5<br>输出样例：<br>3<br>1 4 5<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int MAXN = 100010;</span><br><span class="line">const int INF = 0x7fffffff;</span><br><span class="line">int a[MAXN], leftMax[MAXN], rightMin[MAXN];</span><br><span class="line">int ans[MAXN], num = 0;</span><br><span class="line">int main()&#123;</span><br><span class="line">	int n;</span><br><span class="line">	scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">	for (int i = 0 ; i &lt; n ; i++ ) &#123;</span><br><span class="line">		scanf(&quot;%d&quot;, &amp;a[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	leftMax[0] = 0;</span><br><span class="line">	for (int i = 1 ; i &lt; n ; i++) &#123;</span><br><span class="line">		leftMax[i] = max(leftMax[i - 1], a[i - 1]);</span><br><span class="line">	&#125;</span><br><span class="line">	rightMin[n - 1] = INF;</span><br><span class="line">	for (int i = n - 2 ; i &gt;=0 ; i--) &#123;</span><br><span class="line">		rightMin[i] = min(rightMin[i + 1],a[i + 1]);</span><br><span class="line">	&#125;</span><br><span class="line">	for (int i = 0; i &lt; n ;i++) &#123;</span><br><span class="line">		if(leftMax[i] &lt; a[i] &amp;&amp; a[i] &lt; rightMin[i])&#123;</span><br><span class="line">			ans[num++] = a[i];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	printf(&quot;%d\n&quot;,num);</span><br><span class="line">	for (int i = 0; i &lt; num;i++ )&#123;</span><br><span class="line">		printf(&quot;%d&quot;, ans[i]);</span><br><span class="line">		if(i &lt; num -1)printf(&quot; &quot;);</span><br><span class="line">	&#125; </span><br><span class="line">	printf(&quot;\n&quot;);</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/12/150/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/12/150/" itemprop="url">PAT A1029</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-12T18:21:00+00:00">
                2017-02-12
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.</p>
<p>Given two increasing sequences of integers, you are asked to find their median.</p>
<p>Input</p>
<p>Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (&lt;=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.</p>
<p>Output</p>
<p>For each test case you should output the median of the two given sequences in a line.</p>
<p>Sample Input<br>4 11 12 13 14<br>5 9 10 15 16 17<br>Sample Output<br>13</p>
<p>像merge一样的题<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">//#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 1000010;</span><br><span class="line">const int INF = 0x7fffffff;</span><br><span class="line">int s1[maxn], s2[maxn];</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, m;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;s1[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;m);</span><br><span class="line">    for (int i = 0 ; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;s2[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    s1[n] = INF;</span><br><span class="line">    s2[m] = INF;</span><br><span class="line">    int median = (n + m - 1) / 2;</span><br><span class="line">    int i = 0, j = 0, count = 0;</span><br><span class="line">    while (count &lt; median) &#123;</span><br><span class="line">        if (s1[i] &lt; s2[j]) i++;</span><br><span class="line">        else j++;</span><br><span class="line">        count++;</span><br><span class="line">    &#125;</span><br><span class="line">    if (s1[i] &lt; s2[j]) &#123;</span><br><span class="line">        printf(&quot;%d\n&quot;, s1[i]);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;%d\n&quot;, s2[j]);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/12/147/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/12/147/" itemprop="url">PAT B1035/A1089</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-12T16:29:00+00:00">
                2017-02-12
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>According to Wikipedia:</p>
<p>Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.</p>
<p>Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.</p>
<p>Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line gives a positive integer N (&lt;=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.</p>
<p>Sample Input 1:<br>10<br>3 1 2 8 7 5 9 4 6 0<br>1 2 3 7 8 5 9 4 6 0<br>Sample Output 1:<br>Insertion Sort<br>1 2 3 5 7 8 9 4 6 0<br>Sample Input 2:<br>10<br>3 1 2 8 7 5 9 4 0 6<br>1 3 2 8 5 7 4 9 0 6<br>Sample Output 2:<br>Merge Sort<br>1 2 3 8 4 5 7 9 0 6<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">//#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int N = 110;</span><br><span class="line">int origin[N], tempOri[N], changed[N];</span><br><span class="line">int n;//元素个数</span><br><span class="line">bool isSame(int A[], int B[])&#123;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        if (A[i] != B[i]) return false;</span><br><span class="line">    &#125;</span><br><span class="line">    return true;</span><br><span class="line">&#125;</span><br><span class="line">void showArray(int A[])&#123;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, A[i]);</span><br><span class="line">        if (i &lt; n - 1) printf(&quot; &quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;\n&quot;);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">bool insertSort()&#123;</span><br><span class="line">    bool flag = false;//记录是否存在数组中间步骤与changed数组相同</span><br><span class="line">    for (int i = 1; i &lt; n; i++) &#123;</span><br><span class="line">        if (i != 1 &amp;&amp; isSame(tempOri, changed)) &#123;</span><br><span class="line">            flag = true;</span><br><span class="line">        &#125;</span><br><span class="line">        int temp = tempOri[i], j = i;</span><br><span class="line">        while (j &gt; 0 &amp;&amp; tempOri[j - 1] &gt; temp) &#123;</span><br><span class="line">            tempOri[j] = tempOri[j - 1];</span><br><span class="line">            j--;</span><br><span class="line">        &#125;</span><br><span class="line">        tempOri[j] = temp;</span><br><span class="line">        if (flag == true) &#123;</span><br><span class="line">            return true;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return false;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void mergeSort()&#123;</span><br><span class="line">    bool flag = false;</span><br><span class="line">    for (int step = 2; step / 2 &lt; n; step *=2) &#123;</span><br><span class="line">        if (step != 2 &amp;&amp; isSame(tempOri, changed)) &#123;</span><br><span class="line">            flag = true;</span><br><span class="line">        &#125;</span><br><span class="line">        for (int i = 0; i &lt; n; i += step) &#123;</span><br><span class="line">            sort(tempOri + i, tempOri + min(i + step, n));</span><br><span class="line">        &#125;</span><br><span class="line">        if (flag == true) &#123;</span><br><span class="line">            return;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n ; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;origin[i]);</span><br><span class="line">        tempOri[i] = origin[i];</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;changed[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    if (insertSort()) &#123;</span><br><span class="line">        printf(&quot;Insertion Sort\n&quot;);</span><br><span class="line">        showArray(tempOri);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;Merge Sort\n&quot;);</span><br><span class="line">        for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">            tempOri[i] = origin[i];</span><br><span class="line">        &#125;</span><br><span class="line">        mergeSort();</span><br><span class="line">        showArray(tempOri);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>陷阱：<br>原始序列不参与是否与目标序列相同的比较<br>给定下列样例测试<br>//input<br>4<br>3 4 2 1<br>3 4 2 1<br>//output<br>Inertion Sort<br>2 3 4 1</p>
<p>2017年02月24日补充：<br>此题类似<a href="http://blog.hemisu.com/archives/220/" target="_blank" rel="noopener">A1098</a></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/12/141/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/12/141/" itemprop="url">PAT A1044</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-12T14:51:00+00:00">
                2017-02-12
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:</p>
<ol>
<li>Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15).</li>
<li>Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).</li>
<li>Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).<br>Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.</li>
</ol>
<p>If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 numbers: N (&lt;=105), the total number of diamonds on the chain, and M (&lt;=108), the amount that the customer has to pay. Then the next line contains N positive numbers D1 … DN (Di&lt;=103 for all i=1, …, N) which are the values of the diamonds. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print “i-j” in a line for each pair of i &lt;= j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.</p>
<p>If there is no solution, output “i-j” for pairs of i &lt;= j such that Di + … + Dj &gt; M with (Di + … + Dj - M) minimized. Again all the solutions must be printed in increasing order of i.</p>
<p>It is guaranteed that the total value of diamonds is sufficient to pay the given amount.</p>
<p>Sample Input 1:<br>16 15<br>3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13<br>Sample Output 1:<br>1-5<br>4-6<br>7-8<br>11-11<br>Sample Input 2:<br>5 13<br>2 4 5 7 9<br>Sample Output 2:<br>2-4<br>4-5</p>
<p>求等于S的子串：<br>思路，先令Sum表示1-i的值，这样做的好处是如果想知道3-5的和只要计算Sum[5]-Sum[2]就可以了<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">//#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;algorithm&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//using namespace std;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">int sum[maxn];</span><br><span class="line">int n, S, nearS = 100000010;</span><br><span class="line">//upper_bound 函数返回在[L,R]内第一个大于x的位置</span><br><span class="line">int upper_bound(int L, int R, int x)&#123;</span><br><span class="line">    int left = L, right = R, mid;</span><br><span class="line">    while (left &lt; right) &#123;</span><br><span class="line">        mid = (left + right) / 2;</span><br><span class="line">        if (sum[mid] &gt; x) &#123;</span><br><span class="line">            right = mid;</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            left = mid + 1;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return left;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;S);</span><br><span class="line">    sum[0] = 0;</span><br><span class="line">    for (int i = 1; i &lt;= n ; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;sum[i]);</span><br><span class="line">        sum[i] += sum[i - 1];</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;//遍历左端点</span><br><span class="line">        int j = upper_bound(i, n + 1, sum[i - 1] + S);//找右端点</span><br><span class="line">        if (sum[j - 1] - sum[i - 1] == S) &#123;</span><br><span class="line">            nearS = S;//查找成功，最接近S的就是S</span><br><span class="line">            break;</span><br><span class="line">        &#125;else if(j &lt;= n &amp;&amp; sum[j] - sum[i - 1] &lt; nearS)&#123;</span><br><span class="line">            nearS = sum[j] - sum[i - 1];//存在大于S的解并小鱼nearS</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++)&#123;</span><br><span class="line">        int j = upper_bound(i, n + 1, sum[i - 1] + S);//找右端点</span><br><span class="line">        if(S == nearS)&#123;</span><br><span class="line">            if (sum[j - 1] - sum[i - 1] == nearS) &#123;</span><br><span class="line">                printf(&quot;%d-%d\n&quot;, i, j - 1);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            if (sum[j] - sum[i - 1] == nearS) &#123;</span><br><span class="line">                printf(&quot;%d-%d\n&quot;, i, j);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>一会儿j-1一会儿j的原因是，upper_bound函数返回的是第一个大于x的位置<br>当sum[i-1]+s == sum[j] 时 upper_bound返回的值是left + 1,此时需要-1；<br>而找不到sum[i-1]+s == sum[j]时会返回一个最小的大于S的位置为left + 1，此时不需要-1。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/12/140/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/12/140/" itemprop="url">PAT A1010</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-12T14:50:15+00:00">
                2017-02-12
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is “yes”, if 6 is a decimal number and 110 is a binary number.</p>
<p>Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case occupies a line which contains 4 positive integers:<br>N1 N2 tag radix<br>Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z} where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number “radix” is the radix of N1 if “tag” is 1, or of N2 if “tag” is 2.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print “Impossible”. If the solution is not unique, output the smallest possible radix.</p>
<p>Sample Input 1:<br>6 110 1 10<br>Sample Output 1:<br>2<br>Sample Input 2:<br>1 ab 1 2<br>Sample Output 2:<br>Impossible<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long LL;</span><br><span class="line">LL Map[256];</span><br><span class="line">LL inf = (1LL &lt;&lt; 63) - 1;//long long的最大值2^63-1</span><br><span class="line">void init()&#123;</span><br><span class="line">    for (char c = &apos;0&apos;; c &lt;= &apos;9&apos;; c++) &#123;</span><br><span class="line">        Map[c] = c - &apos;0&apos;;</span><br><span class="line">    &#125;</span><br><span class="line">    for (char c = &apos;a&apos;; c &lt;= &apos;z&apos;; c++) &#123;</span><br><span class="line">        Map[c] = c - &apos;a&apos; + 10;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">LL convertNum10(char a[], LL radix, LL t)&#123;</span><br><span class="line">    LL ans = 0;</span><br><span class="line">    int len = strlen(a);</span><br><span class="line">    for (int i = 0; i &lt; len; i++) &#123;</span><br><span class="line">        ans = ans * radix + Map[a[i]]; //进制转换</span><br><span class="line">        if(ans &lt; 0 || ans &gt; t) return -1;//溢出或者超过N1的十进制</span><br><span class="line">    &#125;</span><br><span class="line">    return ans;</span><br><span class="line">&#125;</span><br><span class="line">int cmp(char N2[], LL radix,LL t)&#123;//N2的十进制与t比较</span><br><span class="line">    int len = strlen(N2);</span><br><span class="line">    LL num = convertNum10(N2, radix, t);//将N2转换为radix进制</span><br><span class="line">    if (num &lt; 0) return 1;//溢出，肯定是N2 &gt; t</span><br><span class="line">    if (t &gt; num) return  -1;//t较大，返回-1</span><br><span class="line">    else if(t == num) return 0;//相等，返回0</span><br><span class="line">    else return 1;//num较大，返回1</span><br><span class="line">&#125;</span><br><span class="line">LL binarySearch(char N2[], LL left, LL right, LL t)&#123;</span><br><span class="line">    LL mid;</span><br><span class="line">    while (left &lt;= right) &#123;</span><br><span class="line">        mid = (left + right)/2;</span><br><span class="line">        int flag = cmp(N2, mid, t);</span><br><span class="line">        if (flag == 0) return mid;</span><br><span class="line">        else if (flag == -1) left = mid + 1;</span><br><span class="line">        else right = mid - 1;</span><br><span class="line">    &#125;</span><br><span class="line">    return -1;//解不存在</span><br><span class="line">&#125;</span><br><span class="line">int findLargestDigit(char N2[])&#123;</span><br><span class="line">    int ans = -1, len = strlen(N2);</span><br><span class="line">    for (int i = 0; i &lt; len; i++) &#123;</span><br><span class="line">        if (Map[N2[i]] &gt; ans) &#123;</span><br><span class="line">            ans = Map[N2[i]];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return ans+1;</span><br><span class="line">&#125;</span><br><span class="line">char N1[20], N2[20], temp[20];</span><br><span class="line">int tag,radix;</span><br><span class="line">int main()&#123;</span><br><span class="line">    init();</span><br><span class="line">    scanf(&quot;%s %s %d %d&quot;, N1, N2, &amp;tag, &amp;radix);</span><br><span class="line">    if (tag == 2) &#123;</span><br><span class="line">        strcpy(temp, N1);</span><br><span class="line">        strcpy(N1, N2);</span><br><span class="line">        strcpy(N2, temp);</span><br><span class="line">    &#125;</span><br><span class="line">    LL t = convertNum10(N1, radix, inf);//将N1从radix进制转换为十进制</span><br><span class="line">    LL low = findLargestDigit(N2);//找到N2中数位最大的位+1，当成二分下界</span><br><span class="line">    LL high = max(low, t) + 1;//上界</span><br><span class="line">    LL ans = binarySearch(N2, low, high, t);</span><br><span class="line">    if (ans == -1) printf(&quot;Impossible\n&quot;);</span><br><span class="line">    else printf(&quot;%lld\n&quot;,ans);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/11/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/11/">11</a><span class="page-number current">12</span><a class="page-number" href="/page/13/">13</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/13/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
